1. Field of the Invention
The present invention relates to processing work requests in a data storage hierarchy. More particularly, the invention relates to transferring data between memory levels and the prioritization of the dispatch of work requests in a data storage hierarchy.
2. Discussion of the Related Art
Computers require a host processor including one or more central processing units and a memory facility. The processor manipulates data stored in the memory according to instructions provided to it. The memory must therefore be capable of storing data required by the processor and transferring that data to the processor at a rate capable of making the overall operation of the computer feasible. The cost and performance of computer memory is thus critical to the commercial success of a computer system.
Because today's computers require large quantities of data storage capacity, computer memory is available in many forms A fast but expensive form of memory is main memory, typically comprised of microchips. Other available forms of memory are known as peripheral storage devices and include magnetic direct access storage devices (DASD), magnetic tape storage devices, optical recording devices, and magnetic or optical mass storage libraries. Each of these other types of memory has a greater storage density and thus lower cost than main memory. However, these other memory devices do not provide the performance provided by a main memory. For example, the time required to mount a tape or disk in a tape drive, DASD, or optical disk drive and the time required to properly position the tape or disk beneath the read/write mechanism of the drive cannot compare with the rapid, purely electronic data transfer rate of main memory. It is inefficient to store all of the data in a computer system on but a single type of memory device. Storing all of the data in main memory is too costly and storing all of the data on one of the peripheral storage devices reduces performance.
A typical computer system includes both main memory and one or more types of peripheral storage devices arranged in a data storage hierarchy. The data storage hierarchy arrangement is tailored to the performance and cost requirements of the user. In such a hierarchy, main memory is often referred to as primary data storage, the next level of the hierarchy is often referred to as secondary data storage, and so on. Generally, the highest level of the hierarchy has the lowest storage density capability, highest performance and highest cost. As one proceeds down through the levels of the hierarchy, storage density generally increases, performance generally decreases, and cost generally decreases. By transferring data between different levels of the hierarchy as required, the cost of memory is minimized and performance is maximized. Data is thus stored in main memory only so long as it is expected to be required by the processor. The hierarchy may take many forms, include any number of data storage or memory levels, and may be able to transfer data directly between any two distinct memory levels.
In a typical computer using main memory as primary data storage and a peripheral storage device as secondary data storage, the processor can only access data for executing instructions if the data is stored in main memory. If work to be done by the processor requires data not then stored in main memory, the processor will recall or promote data from the peripheral storage device to main memory. The promotion of data may employ I/0 channels, controllers, or cache memories well known in the art.
The time required for data to be promoted from peripheral storage to main memory must be minimized to prevent any impact on the performance of the processor. The time required to promote data is determined by various characteristics of the particular peripheral storage device and the data storage hierarchy. For example, in the promotion of data from an optical or magnetic disk drive to main memory, assuming the proper disk is already mounted on the drive, the processor must wait while the read/write mechanism or head of the disk drive is positioned radially over the disk track containing the data to be promoted. This delay is known as "seek" time. The processor must also wait until the rotation of the disk brings the relevant data on the track directly underneath the read/write head. This delay is known as "rotational latency". Finally, the processor must wait for the actual electronic transfer of the data sensed by the head.
Several techniques are known for improving the efficiency of data promotion in data storage hierarchies. The IBM Technical Disclosure Bulletin, Vol. 29, No. 5, October 1986, pgs. 1946-1948 discloses minimizing disk seek time by sequencing tasks based on disk access requirements of the tasks. The tasks are examined to determine the location where on a disk the task access is to occur. More particularly, the radial position of the access location relative to the current radial position of the head is examined such that the task next chosen to be performed will require minimal radial movement of the head.
Techniques are also known for minimizing rotational latency. For example, the IBM Technical Disclosure Bulletin, Vol. 12, No. 6, November 1969, pgs. 815-819 discloses the queuing of requests for data transfer according to the rotational position on the disk of the data for which access is required. A distinct queue exists for each sector or rotational position on the disk. As each sector approaches the head, the queue for that particular sector is interrogated and a work request is extracted therefrom and dispatched. Rotational latency is reduced by dispatching only those work requests requiring access to data already in convenient rotational position.
The IBM Technical Disclosure Bulletin, Vol 24, No. 12, May 1982, pgs. 6605-6606 also discloses a technique for improving host processor efficiency. This technique is applicable to a computer system having multiple processors. In such a system, a processor requiring access to a particular peripheral storage device reserves a data path to such device. The work requests remaining outside of a nearly exhausted chain of requests for accessing a particular peripheral data storage device are examined to determine if any such work requests require access to the same peripheral storage device as that for the chain. Such work requests may be generated after the nearly exhausted requests are chained. If such work requests are found, they are secondarily chained to the original chain of requests for that particular peripheral storage device. The data path between the processor and the peripheral storage device may thus be preserved, thereby preventing another processor from reserving the relinquished data path to the same peripheral device. If another processor was to gain access to that data path, and all other data paths to that peripheral storage device were in use, the processor which relinquished the data path would not be able to resume communication with the peripheral storage device, as required.
Although each of the aforementioned techniques improves data transfer in a data storage hierarchy, thus improving processor efficiency, further improvements are possible. None of the aforementioned techniques reduces the number of storage device I/O cycles required to be devoted to the transfer of data between levels of the data storage hierarchy. Each of the aforementioned techniques requires a distinct storage device I/O cycle or device access for each unit of data that is required to be promoted. If the number of such cycles required is reduced, the efficiency of the system is clearly improved.
Some techniques are known for reducing the number of device accesses required to peripheral storage devices. U.S. Pat. No. 4,583,166 discloses the promotion of the entire track of data containing the record(s) to which access is required for a work request. The promotion of additional data permits the processor, upon needing access to other record(s) from the promoted track, to retrieve such other record(s) from main memory instead of the peripheral storage device. Because some of the data required by the processor is promoted to main memory in advance, the speed with which the processor gains access to that data is increased. This technique is particularly useful where all of the data on the track is related such that access to any particular record on that track indicates a likelihood that other data on that track will also be accessed in the future.
U.S. Pat. Nos. 4,399,503 and 4,490,782 also disclose the promotion of data in addition to that immediately required by the processor. In U.S. Pat. No. 4,399,503 the additional data is simply a fixed number of additional data records sequentially located on the disk after the required record. Again, the promotion of additional data may reduce the number of accesses to the disk required by the processor. In U.S. Pat. No. 4,490,782, the additional data is determined by an index linking data records both likely to be accessed within a certain period of time. Thus, when some of the records from a linked group of data is accessed, additional records from that group are also promoted.
Although the promotion of data in addition to that immediately required by the processor will reduce peripheral storage device accesses, there is no guarantee that such additionally promoted data will actually be next used by the processor. If the level of storage to which data is to be promoted is filled, some of the data thereon will be demoted to a lower level in the hierarchy to make room for the incoming data. It is thus possible for additionally promoted data to migrate out of the level of the hierarchy to which it was promoted before the processor attempts to access such data at the promoted level of the hierarchy. In such instances, there is no improvement to the efficiency of the hierarchy because the promotion of additional data was not useful to the processor. The aforementioned techniques are thus dependent on the likelihood of access to the additionally promoted data before that data migrates back out of the hierarchy level to which it was promoted.